In the ATM standard two basic types of connections can be setup each with its corresponding connection identification mechanism:
Nonterminating virtual path connections. In this case only the VPI entry is used to identify the connection. PA1 Terminating virtual path connections. In this case both the VPI and VCI entries are used to identify the connection.
Depending on the location of the forwarding device within an ATM network, incoming connections may be terminating, nonterminated, or a mix of the two. In order to support all possible header entries at such a device, a very large table (i.e. 2 28 or about 256 million entries would be required. However, in the case of nonterminated virtual paths, all possible VCI values are part of a single connection, reserving additional entries is inherently very wasteful, In the case of terminated virtual paths, relatively few of the 2 16 or about 65 thousand possible VCI entries are used per VPI. In most cases, the number of active VCIs varies among the terminated VPIs.
The ability to configure a lookup mechanism in an efficient manner is thus necessary, but not sufficient. In computer networks connections have finite lifetime. When previously active VCIs in a terminated virtual path become idle, it would be desirable to enable the mechanism to reclaim the memory for use by another virtual path. Similarly, it would be desirable for an active virtual path connection to be able to expand its available number of VCI entries upon demand during operation. These operations that manage the table memory should not affect current operation of the mechanism.
The information can be any of (or a combination of) static or dynamic data. Static and dynamic simply refer to the status of the data stored relative to individual cell time. Examples of static data would include routing information and header translation values, these are generally updated in software. Data types that are dynamic in nature could include connection counters, encryption keys, and bandwidth monitoring values. Dynamic data may be changed on every cell arrival time for that connection. This complicates management of the table memory.
Additionally, the connection information should be protected to ensure that only the connection that the information belongs to can access it. This is a requirement for the mechanism to ensure data on a VCI cannot be corrupted by potentially unmapped connections. Furthermore, to implement the mechanism at a low cost, standard RAMs should be usable for storing the information.
Several existing implementations currently use Content Addressable Memories (CAMs) to perform most of the aforementioned functions; however, the amount of logic contained within these memories makes them significantly more expensive than standard RAMs. A prior art mechanism designed to address the problem of ATM cell dispatching (See U.S. Pat. No. 5,479,401) addresses the issue of utilizing standard RAMs, but does not enable provisions for efficient memory management. The present invention overcomes the limitations of the prior art mechanism by providing a means by which memory may efficiently be accessed and managed with the use of standard RAMs while protecting the information from being accessed by connections besides the one with which it is associated.
In the prior art system, every VCI entry would have to be copied to a new location, then have the VCI Index in the VPI table changed to point to this table. This requires time and extra contiguous space on the order of the size of the VCI table. This could be performed by continuous background compression of the VCI tables.
In the present invention, only the active entries in a Range Table need be relocated. The entries represent a block of PerConnection information in a Sub Table. For blocks sizes of 32 connections each, this mechanism could easily speed relocation by a factor of 100 or more. (Actual speedup depends on the size of the PerConnection information, the number of entries grouped into a block in the Sub Table, and the size of the Range Table entries.) Furthermore, because the entries in the Range Table need not be valid (in use), a wider range can be pre-allocated than is necessary without consuming actual space in the Sub Table.
Furthermore, by controlling access to the Sub Table or lowest level table, a secure transmission of ATM cells across an ATM network can be accomplished. Thus, the problem of preventing undesirable parties obtain the ATM cells as they travel along the ATM network can be solved. In addition, encryption techniques can be employed by sending encrypted (or by encrypting) payloads which can only be decrypted by proper access to encryption keys, for instance, in the lowest level table lookup mechanism.